扁平化多级双向链表

题目描述：多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

示例 1：
输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：
输入的多级列表如下图所示：

扁平化后的链表如下图：

示例 2：
输入：head = [1,2,null,3]
输出：[1,3,2]
解释：
输入的多级列表如下图所示：

1—2—NULL
|
3—NULL

示例 3：
输入：head = []
输出：[]

方法一：迭代利用栈

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

class Solution {
  public Node flatten(Node head) {
    if (head == null) return null;
    LinkedList<Node> stack = new LinkedList<>();
    Node cur = head;
    while (true) {
      if (cur.child != null) {
        // 将 next 节点入栈
        if (cur.next != null) {
          stack.push(cur.next);
        }
        // 将子链表扁平化
        cur.next = cur.child;
        cur.child.prev = cur;
        cur.child = null;
      }
      // 遍历子链表的下一个节点或是从栈中弹出 next 节点
      if (cur.next != null) {
        cur = cur.next;
      } else if (!stack.isEmpty()) {
        Node next = stack.pop();
        cur.next = next;
        next.prev = cur;
        cur = next;
      } else {
        return head;
      }
    }
  }
}

复杂度分析

时间复杂度：O(N)。
空间复杂度：O(N)。

复杂度分析

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：36.5 MB, 在所有 Java 提交中击败了52.57%的用户

方法二：递归

在这里插入图片描述

class Solution {
  public Node flatten(Node head) {
    if (head == null) return null;
    Node cur = head;
    // 向后遍历
    while (cur != null) {
      // 存在子链表，进行递归
      if (cur.child != null) {
        // 保留 next 节点
        Node next = cur.next;
        // 得到扁平化后的子链表，与之相连
        Node child = flatten(cur.child);
        cur.next = child;
        child.prev = cur;
        cur.child = null;
        // 连接原 next
        if (next != null) {
          while (cur.next != null) {
            cur = cur.next;
          }
          cur.next = next;
          next.prev = cur;
        }
      }
      cur = cur.next;
    }
    return head;
  }
}

复杂度分析

时间：O(N)。N 指的是列表的节点数
空间：O(N)，N 指的是列表的节点数，节点仅通过 child 指针相互链接，则在递归调用的过程中堆栈的深度会达到 N

复杂度分析

执行用时：2 ms, 在所有 Java 提交中击败了11.74%的用户
内存消耗：36.4 MB, 在所有 Java 提交中击败了65.39%的用户

方法一：迭代 利用栈

方法二：递归

方法一：迭代利用栈